public class Sort {
    //选择排序
    public void selectSort(int[] arr){
        for(int i = 0;i<arr.length;i++){
            int j = i+1;                //j在i的前一个数，j向后寻找比i下标值小的数，找到了就和i下标的值交换，找不到就向后移动
            int minIndex = i;
            for(;j<arr.length;j++){
                if(arr[j]<arr[minIndex]){
                    minIndex=j;         //跟新最小值下标
                }
            }
            //循环结束后，找到了i前面的最小值小标
            //将i的位置和最小值下标交换
            Swap(arr,i,minIndex);

        }

    }
    public void selectSort2(int[] arr){
        int left = 0;
        int right = arr.length-1;
        while (left<right){
            int j = left+1;
            int minIndex = left;
            int maxIndex = left;
            for(;j<=right;j++){
                if(arr[j]<arr[minIndex]){
                    minIndex=j;
                }
                if(arr[j]>arr[maxIndex]){
                    maxIndex=j;
                }
            }
            if(maxIndex==left){
                maxIndex=minIndex;
            }
            Swap(arr,left,minIndex);
            Swap(arr,right,maxIndex);
            left++;
            right--;

        }

    }


    private static void Swap(int[] arr,int a,int b){
        int tmp = arr[a];
        arr[a]=arr[b];
        arr[b]=tmp;

    }

    //冒泡排序
    public void bubbleSort(int[] arr){
        int len = arr.length;
        for (int i = 0; i < len; i++) {
            for (int j = i+1; j <len ; j++) {
                if(arr[i]>arr[j]){
                    Swap(arr,i,j);
                }
            }

        }
    }


    //插入排序
    //每次循环i前面的值都是有序的
    public void insertSort(int[] arr){

        for (int i = 1; i < arr.length; i++) {
            int j = i-1;        //j定义为i的前一个数
            int tmp = arr[i];   //将arr[i]设置为临时变量，插入i前面有序的数组中
            for(;j>=0;j--){

                if(arr[j]>tmp){
                    arr[j+1]=arr[j];
                }else {
                    //代表前面已经有序了
                    //arr[j+1]=tmp;       //将tmp放回到原来的位置
                    break;
                }
            }
            arr[j+1]=tmp;       //跳出循环的时候，j已经小于0了,

        }

    }
    //希尔排序
    public void shellSort(int[] arr){
        int gap = arr.length;   //gap分的组，
        while (gap>1){
            gap = gap/3 +1 ;
            shell( arr , gap);      //将分好的组进行插入排序
        }

    }
    private void shell(int[] arr, int gap){         //这里和插入排序思路一样，只是插入排序中，我们按照1来进行1来进行计算，这里按照gap来进行计算
                                                    //建议：先把插入排序写完，再写希尔排序
        for(int i = gap;i<arr.length;i++){
            int j = i-gap;
            int tmp = arr[i];

            for(;j>=0;j-=gap){
                if(arr[j]>tmp){
                    arr[j+gap]=arr[j];              //大的数后移
                }else {
                    break;
                }
            }
            arr[j+gap]=tmp;
        }
    }

    //堆排序
    //堆排序首先需要创建大根堆，
    public void headSort(int[] arr){
        //先将数组变成大根堆
        createBigHead(arr);
        int end = arr.length -1;
        while (end > 0){
            Swap(arr,0,end);            //交换头和最后一位节点进行向下调整
            shiftDown(arr,0,end);
            end--;
        }
    }

    //创建大根堆/采用向下调整的方法
    public void createBigHead(int [] arr){
        int end = arr.length;
       int parent = (arr.length-1-1)/2;         //最后一颗子树的父亲节点，开始向下调整
        for(;parent>=0;parent--){
            shiftDown(arr,parent,end);
        }
    }
    private static void shiftDown(int[] arr,int parent,int end){
        int child = 2*parent +1 ;               //左孩子节点
        while (child<end){
            //找出孩子节点中最大的一个，和父亲节点进行交换
            if(child+1<end&&arr[child]<arr[child+1]){
                child=child+1;
            }
            if(arr[child]>arr[parent]){
                Swap(arr,child,parent);
                //交换完成后父亲和孩子节点向下调整
                parent=child;
                child = 2*parent+1;
            }else {
                break;
            }
        }

    }

    public void quickSort(int [] arr){
        int start = 0;              //设置开始和结束
        int end = arr.length-1;
        quick(arr,start,end);       //调用方法
    }
    public void quick(int[] arr,int start,int end){

        if(start>=end){         //当开始大于结束时，递归结束
            return;
        }
        int pivot = partition2(arr,start,end);

        quick(arr,pivot+1,end);

        quick(arr,start,pivot-1);

    }

    public int partition(int[] arr, int left ,int right){
        int tmp = arr[left];            //设置第一个值为基准
        int i = left;                   //保留第一个值的位置

        while (left<right){
            while (left<right&&arr[right]>=tmp){
                right--;                            //从右边开始找，找到比tmp小的值让后停下来
            }


            while (left<right&&arr[left]<=tmp){     //第一个判定条件是防止整个数组的值都比tmp小，从而导致数组越界
                left++;                             //从左边开始找，找到比tmp大的值让后停下来
            }


            Swap(arr,left,right);                   //交换，两个值，有可能left和right相等，相等就交换自己

        }
        Swap(arr,i,left);                       //把相遇的点和第一位交换
        return left;                            //返回left和right相遇的点

    }

    public int partition2(int [] arr,int left,int right){
        int tmp = arr[left];
        int i = left;
        while (left<right){

            while (left<right&&arr[right]>=tmp){
                right--;
            }
            arr[left]=arr[right];           //右边找到比tmp小的，直接交换


            while (left<right&&arr[left]<=tmp){
                left++;
            }
            arr[right]=arr[left];       //左边找到比tmp大的，直接交换
        }
        arr[left]=tmp;          //将取出的tmp放回到空格处
        return left;
    }

    //归并排序
    public void mergeSort(int[] arr){
        mergeFunc(arr,0,arr.length-1);
    }

    public void mergeFunc(int[] arr,int left,int right){
        if(left>=right){
            return;
        }
        //进行分裂
        int mid = (left+right)/2;
        mergeFunc(arr,left,mid);        //左边
        mergeFunc(arr,mid+1,right);     //右边
        //分裂完后进行合并
        merge( arr, left,mid,right);

    }
    public void merge(int[] arr,int left,int mid,int right){
        int s1 = left;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = right;
        int[] tmp = new int[(right-left)+1];
        int k = 0;
        while (s1<=e1&&s2<=e2){  //代表分裂的这段有数据
            //s1和s2进行比较
           if(arr[s1]<=arr[s2]){
               tmp[k++]=arr[s1++];      //谁小放谁进去
           }else {
               tmp[k++]=arr[s2++];
           }
        }
        while (s1<=e1){              //如果有一个没有数据了，直接把剩下的全放进去
            tmp[k++]=arr[s1++];
        }
        while (s2<=e2){
            tmp[k++]=arr[s2++];
        }

        //再把数据拷贝回原来的数组中
        for (int i = 0; i < k; i++) {
            arr[i+left]=tmp[i];             //拷贝回原来的数据
        }

    }




}
